
public class Backtracking {
	static boolean hasFound = false;

	public static boolean backtracking(MazeNodes path, Maze maze, TreasureHunter th, StateList sl) {
		if (isNotPossibleSolution(path, th))
			return false;
		if (isCycling(path, sl))
			return false;
		if (path.size() > 5 * maze.getNodes().size())
			return false;
		if (isSolution(path)) {
			System.out
					.println("-----------------------------------------------------------------------------------------------------------------------------");
			System.out.print("The path to treasure is:\t");
			path.display();
			System.out.println("The amount of fq available at that point:   "
					+ th.getFq());
			System.out
					.println("-----------------------------------------------------------------------------------------------------------------------------");
//			System.exit(0);
			hasFound = true;
			return true;
		}

		MazeEdges AdjacencyEdges = new MazeEdges();
		AdjacencyEdges = maze
				.getAdjacencyEdges((MazeNode) path.get(path.size() - 1));

		for (MazeEdge edge : AdjacencyEdges) {
			path.add(edge.getDestination());
			gainOrconsumeFood(path, maze, th);
			sl.add(new State(edge.getDestination(), th.getFq()));
			backtracking(path, maze, th, sl);
			if(hasFound)
				return true;
			goBack(path, maze, th);
			path.remove(path.size() - 1);
			sl.remove(sl.size() - 1);
			partialSolutionDisplay(path, AdjacencyEdges, th);
		}
		return hasFound;
	}

	private static void partialSolutionDisplay(MazeNodes path, MazeEdges op,
			TreasureHunter th) {
		System.out.print("The identifier of the current node:\t");
		path.display();
		System.out.print("The available operators:\t");
		op.display();
		System.out.println("The amount of fq available at that point:   "
				+ th.getFq());
		System.out.println();
	}

	private static void gainOrconsumeFood(MazeNodes path, Maze maze,
			TreasureHunter th) {
		if (path.size() >= 2) {
			MazeNode source = (MazeNode) path.get(path.size() - 2);
			MazeNode destination = (MazeNode) path.get(path.size() - 1);
			MazeEdge edge = maze.findMazeEdge(source, destination);
			if (destination.getType() == MazeNode.Type.TROLL
					|| destination.getType() == MazeNode.Type.START)
				th.setFq(th.getFq() - edge.getCost());
			else
				th.setFq(th.getFq() - edge.getCost()
						+ destination.getFood_gain()
						- destination.getFood_consume());

		}
	}

	private static boolean isCycling(MazeNodes path, StateList sl) {
		if (path.size() >= 2) {
			State last = (State) sl.get(sl.size() - 1);
			int len = sl.size() - 1;
			for (int i = 0; i < len; i++) {
				if (last.equals(sl.get(i)))
					return true;
			}
			return false;
		}
		return false;
	}

	private static void goBack(MazeNodes path, Maze maze, TreasureHunter th) {
		if (path.size() >= 2) {
			MazeNode source = (MazeNode) path.get(path.size() - 2);
			MazeNode dest = (MazeNode) path.get(path.size() - 1);
			MazeEdge re = maze.findMazeEdge(source, dest);
			if (dest.getType() == MazeNode.Type.TROLL
					|| dest.getType() == MazeNode.Type.START)
				th.setFq(th.getFq() + re.getCost());
			else
				th.setFq(th.getFq() + re.getCost() - dest.getFood_gain()
						+ dest.getFood_consume());
		}
	}

	private static boolean isSolution(MazeNodes path) {
		MazeNode treasure = (MazeNode) path.get(path.size() - 1);

		return treasure.getType() == MazeNode.Type.TREASURE;
	}

	private static boolean isNotPossibleSolution(MazeNodes path,
			TreasureHunter th) {
		MazeNode dest = (MazeNode) path.get(path.size() - 1);
		if (dest.getType() == MazeNode.Type.TROLL) {
			return true;
		}
		return th.getFq() < 0;
	}
}